package com.lcz.suanfa;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * <pre>
 * <img width="128" height="110" src="https://tse3-mm.cn.bing.net/th/id/OIP-C.en-w_oH-yn2UsSRfWnOsGAHaGY?w=198&h=180&c=7&r=0&o=5&dpr=1.25&pid=1.7" alt="马刺">
 * 作者:     <a href="https://github.com/liuchuanzheng">刘传政</a>
 * 创建时间:  10:49 2022/3/4 0004
 * QQ:      1052374416
 * 电话:     18501231486
 * 描述:
 * </pre>
 */
public class 其他 {
    //位1的个数
    public int hammingWeight(int n) {
        String s = Integer.toBinaryString(n);
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }

    //汉明距离
    public int hammingDistance(int x, int y) {

        return Integer.bitCount(x ^ y);
    }

    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;

    }

    @Test
    public void test_杨辉三角() {
        List<List<Integer>> generate = generate(5);
        System.out.println(generate);


    }

    //杨辉三角
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            if (i == 0) {
                list.add(getRow(i, null));
            } else {
                list.add(getRow(i, list.get(i - 1)));
            }
        }
        return list;
    }

    public List<Integer> getRow(int rowNumber, List<Integer> preRow) {
        ArrayList<Integer> row = new ArrayList<>();
        if (rowNumber == 0) {
            row.add(1);
            return row;
        }
        for (int i = 0; i <= rowNumber; i++) {
            int result = 0;
            if (i == 0) {
                result = preRow.get(0);
            } else if (i == rowNumber) {
                result = preRow.get(preRow.size() - 1);
            } else {
                result = preRow.get(i - 1) + preRow.get(i);
            }
            row.add(result);
        }
        return row;
    }

    @Test
    public void test_有效的括号() {
        isValid("()");


    }

    //有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.size() < 1) {
                    return false;
                }
                Character pop = stack.pop();
                if (c == ')' && pop == '(') {

                } else if (c == '}' && pop == '{') {

                } else if (c == ']' && pop == '[') {

                } else {
                    return false;
                }

            }
        }
        if (stack.size() >= 1) {
            return false;
        }
        return true;
    }

    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length; i++) {
            if (i == nums.length) {
                return i;
            }
            if (nums[i] != i) {
                return i;
            }
        }
        return 0;
    }
}
